package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 373. 查找和最小的K对数字
 * 剑指 Offer II 061. 和最小的 k 个数对
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/18 17:47
 */
public class KSmallestPairs {


    public static void main(String[] args) {
        KSmallestPairs test = new KSmallestPairs();

        //输出:    [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
//        int[] arr1 = {1,7,11};
//        int[] arr2 = {2, 6, 11};
//        int k = 3;

        int[] arr1 = {1, 2};
        int[] arr2 = {3};
        int k = 3;
        List<List<Integer>> lists = test.kSmallestPairs(arr1, arr2, k);
        System.out.println(lists);
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        int[] arr = new int[l1];
        int st = 0;
        int end = 0;
        k = Math.min(k, l1 * l2);
        List<List<Integer>> all = new ArrayList<>(k);
        int n = 0;
        while (n < k) {
            int min = Integer.MAX_VALUE;
            int index = st;
            for (int i = st; i <= end; i++) {
                int v = nums1[i] + nums2[arr[i]];
                if (v < min) {
                    min = v;
                    index = i;
                }
            }
            int a = index;
            int b = arr[index];
            List<Integer> list = new ArrayList<>(2);
            list.add(nums1[a]);
            list.add(nums2[b]);
            all.add(list);
            b++;
            arr[index]++;
            if (b == l2) {
                st++;
            }
            if (b == 1) {
                end = Math.min(l1 - 1, end + 1);
            }
            n++;
        }
        return all;
    }


}
